package cn.edu.zufe.mjt.dfs;

import java.util.*;

/**
 * 深度优先搜索——路径数量统计
 * 题目描述：
 * 给定一张有向无环图，图中的节点编号从1到n。图的边是有向的，每条边由一个起点和终点组成。
 * 在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图(DAG图)。
 * 图的存储方式采用邻接表，即对于每个节点u，它的所有出边存储在一个列表中。请你求出从节点s到节点t之间有多少条不同的路径。
 * 输入:
 * 第一行输入两个整数n和 m(2 ≤ n ≤  30,1 ≤ m ≤ 120)，分别表示图中节点的数量和边的数量。
 * 接下来 m 行，每行包含两个整数u 和 υ(1 ≤ u,υ ≤ n)，表示从节点u 到节点υ有一条有向边。
 * 最后一行输入两个整数s和t(1 ≤ s,t ≤ n)，表示起点和终点。
 * 输出:
 * 输出一个整数，表示从节点s到节点t之间的不同路径数。如果没有这样的路径，则输出 0。
 */
public class PathCount {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph.get(u - 1).add(v - 1);
        }
        int s = scanner.nextInt();
        int t = scanner.nextInt();
        int[] memo = new int[n];

        System.out.println(dfs(graph, s - 1, t - 1,memo));


    }

    public static int dfs(List<List<Integer>> graph, int s, int t) {
        if (s == t) {
            return 1;
        }
        int paths = 0;
        for (int v : graph.get(s)) {
            paths += dfs(graph, v, t);
        }
        return paths;
    }

    // n层节点，每层 m 个节点，上一层每个节点都与下一层的 m 个节点相连
    public static List<List<Integer>> generateGraphN(int n, int m) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n*m; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m; j++) {
                graph.get(i*m + j).add(i+m+j);
                System.out.println("from：" + (i*m + j + 1) + " to：" + (i+m+j+1));
            }
        }
        return graph;
    }

    // 记忆化搜搜优化，在递归时，根据访问过的节点的路经，记录该节点的路径数量，降低复杂度
    public static int dfs(List<List<Integer>> graph, int s, int t, int[] memo) {
        if (s == t) {
            return 1;
        }
        int paths = 0;
        for (int v : graph.get(s)) {
            if(memo[v] == 0){
                paths += dfs(graph, v, t, memo);
            } else {
                paths += memo[v];
            }
        }
        memo[s] = paths;
        return paths;
    }

    public static int dfs(Graph graph, int s, int t) {
        if (s == t) {
            return 1;
        }
        int paths = 0;
        for (int v : graph.getAdj()[s]) {
            paths += dfs(graph, v, t);
        }
        return paths;
    }


    // 随机生成有向图
    public static List<List<Integer>> generateGraph(int n, int m) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = (int) (Math.random() * n) + 1;
            int v = (int) (Math.random() * n) + 1;
            graph.get(u - 1).add(v - 1);
        }
        return graph;
    }

    public static Graph generateRandomDirectedGraph(int numNodes, int numEdges) {
        if (numEdges > numNodes * (numNodes - 1)) {
            throw new IllegalArgumentException("边的数量过多，无法在给定的节点数中形成有效的有向图。");
        }

        Graph graph = new Graph(numNodes);
        Random random = new Random();

        Set<String> edgesSet = new HashSet<>();
        while (edgesSet.size() < numEdges) {
            int startNode = random.nextInt(numNodes);
            int endNode = random.nextInt(numNodes);
            if (startNode != endNode) {
                String edge = startNode + "-" + endNode;
                if (!edgesSet.contains(edge)) {
                    edgesSet.add(edge);
                    graph.addEdge(startNode, endNode);
                }
            }
        }

        return graph;
    }

    static class Graph {
        private final int V;
        private final List<Integer>[] adj;

        public Graph(int V) {
            this.V = V;
            adj = new List[V];
            for (int v = 0; v < V; v++) {
                adj[v] = new ArrayList<>();
            }
        }

        public void addEdge(int v, int w) {
            adj[v].add(w);
        }

        public int getV() {
            return V;
        }

        public List<Integer>[] getAdj() {
            return adj;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int v = 0; v < V; v++) {
                sb.append(v).append(": ");
                for (int w : adj[v]) {
                    sb.append(w).append(" ");
                }
                sb.append("\n");
            }
            return sb.toString();
        }
    }

}
